package com.zj.leetcode.medium.greed;

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @program: algorithm
 * @description: 最长数对链
 * 646 maximum-length-of-pair-chain
 * @author: Zhang Bo
 * @create: 2022-03-28 10:34:46
 **/
public class MaximumLengthOfPairChain {
    public static void main(String[] args) {
//        int[][] pairs = {{1,2},{7,8},{4,5}};
        int[][] pairs = {{1,5},{7,8},{1,2},{2,3},{3,4},{5,6},{6,7}};
//        int[][] pairs = {{9,10},{-9,9},{-6,1},{-4,1},{8,10},{7,10},{9,10},{2,10}};
        Solution solution = new MaximumLengthOfPairChain().new Solution();
        System.out.println(solution.findLongestChain(pairs));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int findLongestChain(int[][] pairs) {
            List<int[]> list =
                    Arrays.stream(pairs)
                            .sorted((a, b) -> {
                                return Integer.compare(a[1], b[1]);
                            }).collect(Collectors.toList());

            System.out.println(Arrays.deepToString(list.toArray()));

            int size = 1;
            int left = list.get(0)[1];
            for (int i = 1; i < list.size(); i++) {
                if(left < list.get(i)[0]){
                    size++;
                    left = list.get(i)[1];
                } else {

                }
            }
            return size;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
